package list.p3_singlelist;

public class MySingleList implements IList{
    private static class Node {
        int val;
        Node next;

        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

    private Node head = new Node(0, null);
    @Override
    public void addFirst(int data) {
        Node newNode = new Node(data, null);
        newNode.next = head.next;
        head.next = newNode;
    }

    private Node getLast() {
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        return cur;
    }

    private Node getNode(int index) {
        Node cur = head;
        while (index-- > 0) {
            cur = cur.next;
        }
        return cur;
    }

    @Override
    public void addLast(int data) {
        Node newNode = new Node(data, null);
        Node last = getLast();
        last.next = newNode;
    }

    @Override
    public void addIndex(int index, int data) {
        Node newNode = new Node(data, null);
        Node prev = getNode(index - 1);
        newNode.next = prev.next;
        prev.next = newNode;
    }

    @Override
    public boolean contains(int key) {
        Node cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        Node cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
    }

    @Override
    public void removeAllKey(int key) {
        Node cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
    }

    @Override
    public int size() {
        Node cur = head;
        int size = 0;
        while (cur.next != null) {
            size++;
            cur = cur.next;
        }
        return 0;
    }

    @Override
    public void clear() {
        head = new Node(0, null);
    }

    @Override
    public void display() {
        for (Node cur = head.next; cur != null; cur = cur.next) {
            System.out.print(cur.val + " ");
        }
        System.out.println();
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Node cur = head.next; cur != null; cur = cur.next) {
            sb.append(cur.val).append(" ");
        }
        return sb.toString();
    }

    public void reverse() {
        if (head == null || head.next == null || head.next.next == null) return;
        boolean flag = true;
        for (Node cur = head.next; cur != null; cur = cur.next) {
            if (flag) {
                flag = false;
                head.next = new Node(cur.val, null);
            } else {
                head.next = new Node(cur.val, head.next);
            }
        }
    }

    public int getLastK(int k) {
        if (head.next == null) return -1;
        int size = 0;
        for (Node cur = head.next; cur != null; cur = cur.next, size++);
        if (k > size) return -1;
        Node fast = head.next, slow = head.next;
        while (k-- > 0) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}
